package 代码随想录.数组;

public class _3移除元素 {

    /**
     * 27. 移除元素
     * https://leetcode.cn/problems/remove-element/
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
     */
    public int removeElement(int[] nums, int val) {
        // 快慢指针
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;
    }
    public int removeElement2(int[] nums, int val) {
        //相向双指针
        int k = nums.length -1;
        int i = 0;
        while(i<=k){
            if(nums[i]==val){
//                swap(nums,i,k);
                nums[i] = nums[k];
                k--;
            }else{
                i++;
            }
        }
        return k>=0?k+1:0;
    }

    void swap(int[] nums,int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }


    /**
     * 26. 删除有序数组中的重复项
     * https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
     * 给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
     */
    public int removeDuplicates(int[] nums) {
        int slowIndex = 0;
        for(int fastIndex = 1;fastIndex<nums.length;fastIndex++){
            if(nums[slowIndex]==nums[fastIndex])
                continue;
            else
                nums[++slowIndex] = nums[fastIndex];
        }
        return slowIndex+1;
    }

    /**
     * 283. 移动零
     * https://leetcode.cn/problems/move-zeroes/
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     */
    public void moveZeroes(int[] nums) {
        int slowIndex = 0;
        for(int fastIndex = 0; fastIndex<nums.length;fastIndex++){
            if(nums[fastIndex]!=0){
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        for(int i=slowIndex;i<nums.length;i++)
            nums[i] = 0;
        return;
    }

    /**
     * 844. 比较含退格的字符串
     * https://leetcode.cn/problems/backspace-string-compare/
     * 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
     */
    public boolean backspaceCompare(String s, String t) {
        int i = s.length()-1 , j = t.length()-1;
        int skipS = 0 , skipT =0;

        while (i>=0 || j>=0){
            while(i>=0){
                if(s.charAt(i)=='#'){
                    skipS++;
                    i--;
                }else if(skipS>0){
                    skipS--;
                    i--;
                }else{
                    break;
                }
            }
            while (j >= 0){
                if(t.charAt(j)=='#'){
                    skipT++;
                    j--;
                }else if(skipT>0){
                    skipT--;
                    j--;
                }else{
                    break;
                }
            }

            if(i>= 0 && j>= 0){
                if(s.charAt(i)!=t.charAt(j))
                    return false;
            }else{
                if(i>=0 || j >=0)
                    return false;
            }

            i--;
            j--;
        }
        return true;
    }

    /**
     * 977. 有序数组的平方
     * https://leetcode.cn/problems/squares-of-a-sorted-array/
     * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
     */
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        for (int i = 0, j = n - 1, pos = n - 1; i <= j;) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                ans[pos] = nums[i] * nums[i];
                ++i;
            } else {
                ans[pos] = nums[j] * nums[j];
                --j;
            }
            --pos;
        }
        return ans;
    }
}
